import java.util.*;

public class CoinChange {
    public static void main(String[] args) {
//        int[] coins1 = {1, 2, 5};
//        int amount1 = 11;
//        int[] coins2 = {2};
//        int amount2 = 3;
//        int[] coins3 = {1};
//        int amount3 = 0;
        CoinChange coinChange = new CoinChange();
//        System.out.println(coinChange.coinChange(coins1,amount1));
//        System.out.println(coinChange.coinChange(coins2,amount2));
//        System.out.println(coinChange.coinChange(coins3,amount3));
//        int[] t1 = {1,1,1};
//        int k1 = 2;
//        coinChange.subarraySum(t1,k1);
//        int[] t1 = {3,2,2,3};
//        int k1 = 3;
//        coinChange.removeElement(t1,k1);
//        int[] t1 ={0,1,0,3,12};
//        coinChange.moveZeroes(t1);
        int[][] test= {{1,2},{3},{3},{}};
        coinChange.allPathsSourceTarget(test);
    }
        public int coinChange(int[] coins, int amount) {
            if (amount < 1) {
                return 0;
            }
            return coinChange2(coins, amount);
        }

        private int coinChange2(int[] coins, int rem) {
            if (rem < 0) {
                return -1;
            }
            if (rem == 0) {
                return 0;
            }
            int min = Integer.MAX_VALUE;
            for (int coin : coins) {
                int res = coinChange2(coins, rem - coin);
                if (res >= 0 && res < min) {
                    min = 1 + res;
                }
            }

            return  (min == Integer.MAX_VALUE) ? -1 : min;
        }

    public int coinChange3(int[] coins, int amount) {
        int[] dp = new int[amount+1];
        Arrays.fill(dp,amount+1);
        dp[0] = 0;
        for (int i = 0; i <= amount ; i++) {
            for (int coin : coins) {
                if(coin <= i){
                    dp[i] = Math.min(dp[i],dp[i-coin]+1);
                }
            }
        }
        return dp[amount] >amount ? -1:dp[amount];
    }


    public int findJudge(int n, int[][] trust) {
        int result = -1;
        int[] arr = new int[n];
        for (int[] ints : trust) {
            arr[ints[0]-1] =-1;
            arr[ints[1]-1] +=1;
        }
        for (int i = 0; i < arr.length; i++) {
            if(arr[i] ==n-1){
                result = i+1;
            }
        }
        return result;
    }

    public int subarraySum(int[] nums, int k) {
        int count = 0, pre = 0;
        Map< Integer, Integer > mp = new HashMap< >();
        mp.put(0, 1);
        for (int i = 0; i < nums.length; i++) {
            pre += nums[i];
            System.out.println(pre);
            if (mp.containsKey(pre - k)) {
                count += mp.get(pre - k);
            }
            mp.put(pre, mp.getOrDefault(pre, 0) + 1);
        }
        return count;
    }

    public int removeElement(int[] nums, int val) {
        if(nums.length ==0){
            return 0;
        }
        int left = 0;
        int right = nums.length-1;
        while(left <= right){
            if (nums[left]==val) {
                nums[left] = nums[right--];
            }else {
                left ++;

            }
        }
        return left;
    }

    /**
     * 字符          数值
     * I             1
     * V             5
     * X             10
     * L             50
     * C             100
     * D             500
     * M             1000
     * @return
     */
    public int romanToInt(String s) {
        Map<Character,Integer>  map = new HashMap<>();
        map.put('I',1);
        map.put('V',5);
        map.put('X',10);
        map.put('L',50);
        map.put('C',100);
        map.put('D',500);
        map.put('M',1000);
        int result = 0;
        for (int i = 0; i < s.length(); i++) {
            int temp = map.get(s.charAt(i));
            if(i < s.length()-1 && (map.get(s.charAt(i+1)) >temp)){
                temp*=-1;
            }
            result +=temp;
        }
        return result;
    }

    public String longestCommonPrefix(String[] strs) {
        String result = "";
        if(strs==null || strs.length ==0){
            return result;
        }
        //拆分
        return longestCommonPrefixMergeSort(strs,0,strs.length-1);
    }

    private String longestCommonPrefixMergeSort(String[] strs, int start,int end) {
        if(start==end){
            return strs[start];
        }else{
            int mid = (end-start)/2+start;
            String left = longestCommonPrefixMergeSort(strs,start,mid);
            String right = longestCommonPrefixMergeSort(strs,mid+1,end);
            return longestCommonPrefixService(left,right);
        }
    }

    private String longestCommonPrefixService(String lcpLeft, String lcpRight) {
        int minLength = Math.min(lcpLeft.length(), lcpRight.length());
        for (int i = 0; i < minLength; i++) {
            if (lcpLeft.charAt(i) != lcpRight.charAt(i)) {
                return lcpLeft.substring(0, i);
            }
        }
        return lcpLeft.substring(0, minLength);
    }

    public void moveZeroes(int[] nums) {
        if(nums ==null || nums.length<2){
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if(nums[i] == 0){
                for (int j = i+1; j < nums.length; j++) {
                    if(nums[j] != 0){
                        nums[i] = nums[j];
                        nums[j]=0;
                        break;
                    }
                }
            }
        }
    }

    public void moveZeroesTP(int[] nums) {
        if(nums ==null || nums.length<2){
            return;
        }
        int left =0,right =0;
        while(right<nums.length){
            if(nums[right]!=0){
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
                left++;
            }
            right++;
        }
    }


    public int removeDuplicates(int[] nums) {
        if(nums==null || nums.length <1){
            return 0;
        }
        int slow =1,fast =1;
        while(fast<nums.length){
            if(nums[fast] != nums[fast - 1]){
                nums[slow] = nums[fast];
                slow++;
            }
            fast++;
        }
        return slow;
    }

    public int xorOperation(int n, int start) {
        int result = 0;
        for (int i = 0; i < n; i++) {
            result ^= start +2*i;
        }
        return result;
    }

    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        List<List<Integer>> result = new ArrayList<>();
        if(graph.length>1){
            List<Integer> temp = new ArrayList<>();
            allPathsSourceTargetDG(graph,0,result,temp);
        }
        return result;
    }
    public void allPathsSourceTargetDG(int[][] graph,int startIndex, List<List<Integer>> result,List<Integer> temp){
        int[] routes = graph[startIndex];
        temp.add(startIndex);
        for (int i = 0; i < routes.length; i++) {
            int directIndex = graph[startIndex][i];
            if(directIndex == graph.length -1){
                temp.add(directIndex);
                result.add(new ArrayList<>(temp));
            }else{
                allPathsSourceTargetDG(graph,directIndex,result,temp);
            }
            temp.remove(temp.size()-1);

        }
    }
}
